/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/largest-rectangle-in-histogram
   @Language: C++
   @Datetime: 17-04-14 21:56
   */

class Solution {
public:
	/**
	 * @param height: A list of integer
	 * @return: The area of largest rectangle in the histogram
	 * Tip : Using stack record last ascending order number
	 *       calculate histogram ending with 'largest' number(stack top)
	 * Sketch : 2,3,5,6,2,3
	 *       when traversal height[4]=2, it < stack.top()
	 *       calculate ending with 6 histogram, [5,6], [3,6], [2,6].
	 *       when calculate range[0,5], only need know histogram[0]=2.
	 */
	int largestRectangleArea(vector<int> &height) {
		stack<int> pos;
		int mx = 0;
		for (int i=0; i<=height.size();){
			if(pos.size()<1 || (i<height.size() && height[pos.top()]<height[i]))
				pos.push(i++);		// record current max number pos
			else{
				int h = height[pos.top()];
				pos.pop();
				if (pos.size()) mx = max(mx,(i-pos.top()-1)*h);
				else mx = max(mx, i*h);
			}
		}
		return mx;
	}
};
